/*
 * @lc app=leetcode.cn id=46 lang=cpp
 *
 * [46] 全排列
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        ;
        // int n = nums.size();

        // recursion / trace back

        multiset<int> numsLeft;
        for (auto& num : nums){
            numsLeft.insert(num);
        }

        vector<vector<int>> res;
        vector<int> current{};
        subPermute(current, numsLeft, res);

        return res;
    }

    void subPermute(vector<int>& current, multiset<int>& numsLeft, 
                    vector<vector<int>>& res){
        // showVector(current);
        ;
        int n = numsLeft.size();

        // printf("left %d\n", n);
        if (n == 1){
            int num = *(numsLeft.begin());

            current.push_back(num);
            res.push_back(current);
            current.pop_back();
            return;
        } else{
            for (int i=0;i<n;i++){
                auto numIter = numsLeft.begin();
                for(int ii=0;ii<i;ii++){numIter++;}
                int num = *numIter;

                current.push_back(num);

                numsLeft.erase(numIter);

                subPermute(current, numsLeft, res);

                numsLeft.insert(num);

                current.pop_back();

            }
        }
    }

    // void showVector(vector<int> vec){
    //     for (auto& num : vec){
    //         printf("%d ", num);
    //     }
    //     printf("\n");
    // }

    // 确实直接[0:current]保存current更好，只需要swap

    // void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
    //     // 所有数都填完了
    //     if (first == len) {
    //         res.emplace_back(output);
    //         return;
    //     }
    //     for (int i = first; i < len; ++i) {
    //         // 动态维护数组
    //         swap(output[i], output[first]);
    //         // 继续递归填下一个数
    //         backtrack(res, output, first + 1, len);
    //         // 撤销操作
    //         swap(output[i], output[first]);
    //     }
    // }
    // vector<vector<int>> permute(vector<int>& nums) {
    //     vector<vector<int> > res;
    //     backtrack(res, nums, 0, (int)nums.size());
    //     return res;
    // }
};
// @lc code=end

